package wxy;

import java.util.Map;
import java.util.TreeMap;

public class LeetCode870 {

    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i : nums1) {
            treeMap.compute(i, (k, v) -> v == null ? 1 : v + 1);
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            Map.Entry<Integer, Integer> higherEntry = treeMap.higherEntry(nums2[i]);
            if (higherEntry != null) {
                Integer key = higherEntry.getKey();
                res[i] = key;
                Integer value = higherEntry.getValue();
                if (value == 1) {
                    treeMap.remove(key);
                } else {
                    treeMap.put(key, value - 1);
                }
            } else {
                Map.Entry<Integer, Integer> firstEntry = treeMap.firstEntry();
                Integer key = firstEntry.getKey();
                res[i] = key;
                Integer value = firstEntry.getValue();
                if (value == 1) {
                    treeMap.remove(key);
                } else {
                    treeMap.put(key, value - 1);
                }
            }
        }
        return res;
    }

}
